`
https://leetcode.cn/problems/minimum-time-to-activate-string/
`

/**
 * @param {string} s
 * @param {number[]} order
 * @param {number} k
 * @return {number}
 */
var minTime = function (s, order, k) {
  const n = s.length
  // 所有字符都改成 * 依然无法满足
  if (n * (n + 1) / 2 < k) return -1

  // 存储变成 * 的位置
  const star = new Array(n).fill(-1)

  // 计算前 m 次修改之后的有效字串的数量是否 >= k
  const check = (m) => {
    // 这里传进来的 m 是下标，要查的实际上是 m + 1 次
    // 用 m 表示本次查询里是 * 的位置
    for (let i = 0; i <= m; i++) star[order[i]] = m
    let count = 0
    // 维护 last 表示最近的 '*' 位置
    let last = -1
    for (let i = 0; i < n; i++) {
      const x = star[i]
      if (x === m) last = i
      // 当前枚举到 s[i]，那么如下子串均包含至少一个星号
      // [0, i], [1, i], [2, i], ... , [last, i]
      // 共有 last + 1 个
      count += last + 1
      // 已经比 k 大就没必要继续遍历了
      if (count >= k) return true
    }
    return false
  }

  let left = -1, right = n - 1
  while (left + 1 < right) {
    const mid = left + Math.floor((right - left) / 2)
    // 找到第一个使字符串中有效子串 >= k 的位置
    if (check(mid)) {
      right = mid
    } else {
      left = mid
    }
  }
  return right
};